﻿ #define _CRT_SECURE_NO_WARNINGS 1

 class MedianFinder
 {
	 priority_queue<int> left; // ⼤根堆
	 priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
	 public:
	 MedianFinder()
		 {
	 }
	
		 void addNum(int num)
		 {
		 // 分类讨论即可
			 if (left.size() == right.size()) // 左右两个堆的元素个数相同
			 {
			if (left.empty() || num <= left.top()) // 放 left ⾥⾯
				 {
				 left.push(num);
				 }
			 else
				 {
				 right.push(num);
				 left.push(right.top());
				 right.pop();
				 }
			 }
		 else
			 {
			 if (num <= left.top())
				 {
				 left.push(num);
				 right.push(left.top());
				 left.pop();
				 }
			 else
				 {
				 right.push(num);
				 }
			 }
		 }
	
		 double findMedian()
		 {
		 if (left.size() == right.size()) return (left.top() + right.top()) / 2.0;
		 else return left.top();
		 }
	 };